package offer.leetcode.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * 从尾到头打印链表
 * https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
 * @author DengYuan2
 * @create 2021-01-04 21:04
 */
public class E_06 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        n1.next=n3;
        n3.next=n2;
//        int[] res1 = reversePrint(null);
//        System.out.println(Arrays.toString(res1));
//        int[] res2 = reversePrint2(n1);
//        System.out.println(Arrays.toString(res2));
        int[] res3 = reversePrint3(n1);
        System.out.println(Arrays.toString(res3));

    }

    /**
     * 我的写法
     * @param head
     * @return
     */
    public static int[] reversePrint(ListNode head) {
        //不用这几行，因为为空时要求返回[]
//        if (head==null){
//            return null;
//        }

        ListNode tmp = head;
        int size =0;
        while (tmp!=null){
                size++;
                tmp=tmp.next;
        }
        int[] res = new int[size];
        tmp = head;
        while (tmp!=null){
            res[--size]=tmp.val;
            tmp=tmp.next;
        }
        return res;
    }

    /**
     * 栈
     * @param head
     * @return
     */
    public static int[] reversePrint2(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ListNode tmp = head;
        while (tmp!=null){
            stack.push(tmp.val);
            tmp=tmp.next;
        }
        int size = stack.size();
        int[] res = new int[size];
        //注意：此处要是size,或者res.size(),不能直接写stack.size(),因为pop后stack的大小一直在变啊
        for (int i = 0; i < size; i++) {
            res[i]=stack.pop();
        }
        return res;
    }

    /**
     * 递归
     * @param head
     * @return
     */
    static ArrayList<Integer> list = new ArrayList<>();
    public static int[] reversePrint3(ListNode head){
        reverse3Helper(head);
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }

    public static void reverse3Helper(ListNode head){
        if (head==null){
            return;
        }
        reverse3Helper(head.next);
        list.add(head.val);
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}